-- file zs5/MyRecursive.hs
module MyRecursive where

factorial :: Integer -> Integer
factorial n =
  if n < 0
    then error "n is less than 0"
    else
      if n == 0
        then 1
        else n * factorial (n - 1)

-- 最大公约数
mygcd :: Int -> Int -> Int
mygcd x y
  -- x==0 的情况, 包含在 otherwise 中
  | y == 0 = x
  | otherwise = mygcd y (mod x y)

-- 幂函数, 分奇偶情况 加速
power' :: Int -> Int -> Int
power' 0 0 = 1
power' _ 0 = 1
power' x n
  | odd n = let p = power' x ((n - 1) `div` 2) in x * p * p
  | otherwise = let p = power' x (n `div` 2) in p * p

product' :: (Num a) => [a] -> a
product' [] = 1 -- (1)
product' (x : xs) = x * product' xs -- (2)

-- construct list
cons :: a -> [a] -> [a]
cons = (:)

-- inverse construct
snoc :: a -> [a] -> [a]
snoc x [] = [x]
snoc x (y : ys) = y : snoc x ys

-- 自定义 last
last' :: [a] -> a
last' [] = error "empty list"
last' [x] = x
last' (_ : xs) = last' xs

-- 自定义take
take' :: (Ord n, Num n) => n -> [t2] -> [t2]
take' n _ | n <= 0 = []
take' _ [] = []
take' n (x : xs) = x : take' (n - 1) xs

-- 自定义 drop
drop' :: (Ord n, Num n) => n -> [t2] -> [t2]
drop' n xs | n <= 0 = xs
drop' _ [] = []
drop' n (x : xs) = drop' (n - 1) xs

-- element of
elem' :: (Eq a) => a -> [a] -> Bool
elem' _ [] = False
elem' a (x : xs)
  | a == x = True
  | otherwise = elem' a xs

-- delete
delete' :: (Eq a) => a -> [a] -> [a]
delete' _ [] = []
delete' a (x : xs)
  | a == x = xs
  | otherwise = x : delete' a xs